package leetcode.每日一题.二分查找;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2022/12/20 7:49 PM
 * @description：
 */
public class 两球之间的磁力 {
    @Test
    public void test() {
        System.out.println(new Solution().maxDistance(new int[]{1, 2, 3, 4, 7}, 3));
    }

    class Solution {
        public int maxDistance(int[] position, int m) {
            Arrays.sort(position);
            int left = 1;
            int ans = 0;
            int right = position[position.length - 1] - position[0];
            while (left <= right) {
                int mid = left + right >> 1;
                if (check(position, mid, m)) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return ans;
        }

        private boolean check(int[] position, int mid, int m) {
            int pre = position[0];
            int cnt = 1;
            for (int i = 1; i < position.length; i++) {
                if (position[i] - pre >= mid) {
                    pre = position[i];
                    cnt++;
                }
            }
            return cnt >= m;
        }
    }
}
